package com.sheng.leetcode.year2022.month07.day07;

import org.junit.Test;

import java.util.*;

/**
 * @author liusheng
 * @date 2022/07/07
 *
 * 648. 单词替换
 *
 * 在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。
 * 例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
 * 现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。
 * 你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
 * 你需要输出替换之后的句子。
 *
 * 示例 1：
 * 输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
 * 输出："the cat was rat by the bat"
 *
 * 示例 2：
 * 输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
 * 输出："a a b c"
 *
 * 提示：
 *
 * 1 <= dictionary.length <= 1000
 * 1 <= dictionary[i].length <= 100
 * dictionary[i] 仅由小写字母组成。
 * 1 <= sentence.length <= 10^6
 * sentence 仅由小写字母和空格组成。
 * sentence 中单词的总量在范围 [1, 1000] 内。
 * sentence 中每个单词的长度在范围 [1, 1000] 内。
 * sentence 中单词之间由一个空格隔开。
 * sentence 没有前导或尾随空格。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/replace-words
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0648 {

    @Test
    public void test01(){
//        List<String> dictionary = Arrays.asList("cat", "bat", "rat");
//        String sentence = "the cattle was rattled by the battery";
        List<String> dictionary = Arrays.asList("a","b","c");
        String sentence = "aadsfasf absbs bbab cadsfafs";
        System.out.println(new Solution().replaceWords(dictionary, sentence));
    }

}
class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        //存放已经遇见过的单词，以及对应的词根坐标
        Map<String, Integer> map = new HashMap<>();
        String[] strs = sentence.split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < strs.length; i++) {
            if (map.containsKey(strs[i])) {
                if (map.get(strs[i]) != -1) {
                    strs[i] = dictionary.get(map.get(strs[i]));
                }
            } else {
                int index = -1;
                for (int j = 0; j < dictionary.size(); j++) {
                    //意味着当前字符为继承词
                    if (strs[i].indexOf(dictionary.get(j)) == 0 && index == -1) {
                        index = j;
                    } else if (strs[i].indexOf(dictionary.get(j)) == 0 && index != -1) {
                        if (dictionary.get(index).length() > dictionary.get(j).length()) {
                            index = j;
                        }
                    }
                }
                if (index != -1) {
                    strs[i] = dictionary.get(index);
                }
                map.put(strs[i], index);
            }
            stringBuilder.append(strs[i]).append(" ");
        }
        return stringBuilder.substring(0, stringBuilder.length() - 1);
    }
}

//class Solution {
//    static int N = 100000, M = 26;
//    static int[][] tr = new int[N][M];
//    static boolean[] isEnd = new boolean[N * M];
//    static int idx;
//    void add(String s) {
//        int p = 0;
//        for (int i = 0; i < s.length(); i++) {
//            int u = s.charAt(i) - 'a';
//            if (tr[p][u] == 0) tr[p][u] = ++idx;
//            p = tr[p][u];
//        }
//        isEnd[p] = true;
//    }
//    String query(String s) {
//        for (int i = 0, p = 0; i < s.length(); i++) {
//            int u = s.charAt(i) - 'a';
//            if (tr[p][u] == 0) break;
//            if (isEnd[tr[p][u]]) return s.substring(0, i + 1);
//            p = tr[p][u];
//        }
//        return s;
//    }
//    public String replaceWords(List<String> ds, String s) {
//        for (int i = 0; i <= idx; i++) {
//            Arrays.fill(tr[i], 0);
//            isEnd[i] = false;
//        }
//        for (String d : ds) add(d);
//        StringBuilder sb = new StringBuilder();
//        for (String str : s.split(" ")) sb.append(query(str)).append(" ");
//        return sb.substring(0, sb.length() - 1);
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/replace-words/solution/by-ac_oier-jecf/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
